GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Iterative Tiefensuche</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Iterative Tiefensuche</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Die iterative Tiefensuche (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> iterative deepening depth-first search, IDDFS) ist ein Verfahren aus der <a href="Informatik" title="Informatik">Informatik</a> zum Suchen eines <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knotens</a> in einem <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a>. Der Algorithmus kombiniert die wünschenswerten Eigenschaften von <a href="Tiefensuche" title="Tiefensuche">Tiefensuche</a> (geringer Speicherverbrauch) und <a href="Breitensuche" title="Breitensuche">Breitensuche</a> (Optimalität).

Die iterative Tiefensuche ist wie die normale Tiefensuche eine <a href="Suchalgorithmus#Heuristische_(Informierte)_Suchalgorithmen" class="mw-redirect" title="Suchalgorithmus">uninformierte Suche</a>. Sie funktioniert wie die <a href="Tiefensuche" title="Tiefensuche">Tiefensuche</a>, vermeidet jedoch durch Begrenzung der Suchtiefe deren Nachteile bezüglich Vollständigkeit. Bei der iterativen Tiefensuche wird iterativ eine <a href="Beschr%C3%A4nkte_Tiefensuche" title="Beschränkte Tiefensuche">beschränkte Tiefensuche</a> durchgeführt, und dabei das Level, bis zu welchem die Beschränkte Tiefensuche den <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a> erkundet, bei jeder <a href="Iteration" title="Iteration">Iteration</a> um eins erhöht. Im ersten Schritt werden also alle <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a>, zu denen ein <a href="Pfad_(Graphentheorie)" class="mw-redirect" title="Pfad (Graphentheorie)">Pfad</a> der Länge 0 führt, mittels Tiefensuche erkundet. Im nächsten Schritt werden dann alle Knoten, zu denen ein Pfad der Länge 1 führt, mittels Tiefensuche erkundet und so weiter. Hierdurch wird erreicht, dass Iterative Tiefensuche prinzipiell auf allen Graphen vollständig ist, da die Suche sich nun nicht mehr in einem endlos langen Pfad verlieren kann.

Damit stellt die iterative Tiefensuche eine Kombination der Tiefen- und der <a href="Breitensuche" title="Breitensuche">Breitensuche</a> dar. Sie hat einerseits den gleichen <a href="Platzkomplexit%C3%A4t" title="Platzkomplexität">Speicherplatzverbrauch</a> wie die normale Tiefensuche (im Arbeitsspeicher muss jeweils maximal ein kompletter Ast bis zur momentanen Iterationstiefe gespeichert werden), liefert aber bei monoton steigenden Pfadkosten, ebenso wie die Breitensuche, eine optimale Lösung. Da für jede neue Iteration auch der bereits durchlaufene <a href="Suchbaum" title="Suchbaum">Suchbaum</a> komplett neu aufgebaut werden muss, ist die <a href="Laufzeitkomplexit%C3%A4t" class="mw-redirect" title="Laufzeitkomplexität">Laufzeit</a> höher als bei normaler Tiefensuche. Da in einem Suchbaum aber jeweils der größte Teil der Knoten Blätter sind, ist dieser geringe Mehraufwand gegenüber den Vorteilen hinnehmbar.

<div class="mw-heading mw-heading2"><h2 id="Algorithmus_(informell)">Algorithmus (informell)</h2></div>

<ol><li>Bestimme den Knoten, an dem die Suche beginnen soll</li>

<li>Rufe <a href="Beschr%C3%A4nkte_Tiefensuche" title="Beschränkte Tiefensuche">Beschränkte Tiefensuche</a> mit der aktuellen Suchtiefe auf</li>

<li>Erhöhe die Suchtiefe um 1 und gehe zu Schritt 2</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Algorithmus_(formal)">Algorithmus (formal)</h2></div>

<pre>Iterative Tiefensuche (Knoten, Ziel)

{

IterationsTiefe := 0

while (IterationsTiefe < unendlich)

{

Beschränkte_Tiefensuche (Knoten, Ziel, IterationsTiefe);

IterationsTiefe := IterationsTiefe + 1;

}

</pre>

<div class="mw-heading mw-heading2"><h2 id="Algorithmusbeispiel:_Erzeugen_des_Tiefensuchwaldes_(iterativ)">Algorithmusbeispiel: Erzeugen des Tiefensuchwaldes (iterativ)</h2></div>

Der folgende iterative Algorithmus erzeugt den Tiefensuchwald eines Graphen G mittels Setzen von Discovery- und Finishing-Times und Färben der Knoten. In Anlehnung an <a href="Thomas_H._Cormen" title="Thomas H. Cormen">Cormen</a>, <a href="Charles_Leiserson" class="mw-redirect" title="Charles Leiserson">Leiserson</a>, <a href="Ronald_L._Rivest" title="Ronald L. Rivest">Rivest</a>, <a href="Clifford_Stein" title="Clifford Stein">Stein</a>, Introduction to Algorithms, MIT Press, 2001, werden zunächst alle Knoten weiß gefärbt. Anschließend startet die Tiefensuche per Definition beim alphabetisch kleinsten Knoten und färbt diesen grau. Danach wird ein Stack verwendet, worin der bereits entdeckte Weg bis zu einem Knoten ohne weißen Nachbarn gespeichert wird. Alle Knoten im Stack sind grau.

Der Stack wird abgetragen, bis einer der gespeicherten Knoten noch einen weiteren weißen Nachbarn hat oder der Stack leer ist. Damit wird das der Rekursion eigene <a href="Backtracking" title="Backtracking">Backtracking</a> simuliert.

Die vorgefertigte Methode nextw(u) liefert für einen Knoten u den (per Definition alphabetisch kleinsten) weißen Nachbarn. Existiert kein solcher, liefert sie NULL bzw. FALSE.

<div class="mw-highlight mw-highlight-lang-java mw-content-ltr mw-highlight-lines" dir="ltr"><pre>for each v of G { //Initialisierung:

col[v] = w; //Alle Knoten weiß färben und

pi[v] = null; //Vorgänger auf null setzen

}

time=0;

S=0; //Stack S initialisieren

for each u of G { //für alle weißen Knoten u

if (col[u]==w) {

time++; //Zeitzähler erhöhen

col[u] = g; //Aktuellen Knoten grau färben

d[u] = time; //Entdeckzeit setzen

push(S, u); //Aktuellen Knoten auf Stack

while (S!=0) { //Solange Stack belegt ist

time++; //Zeitzähler erhöhen

v = nextw(u);

if (v!=null) { //wenn nächster weißer Nachbar

col[v] = g; //v grau färben

d[v] = time; //Entdeckzeit setzen

pi[v] = u; //Vorgänger setzen

if (nextw(v)!=null)

push(S, v);

u=v; //Aktueller Knoten ist v

} else { //wenn v NULL

col[u] = s; //Aktuellen Knoten schwarz färben

f[u] = time; //Finishing-Time setzen

if (S!=0)

u = pop(S); //neuer aktueller Knoten von Stack

if (col[u]==g)

push(S,u); //Solange Knoten noch nicht Schwarz, wieder auf den Stack

}

}

}

}

</pre></div>

for each node of adj[u] {

if col[node]==w

return node;

}

return null;

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Speicherplatzverbrauch">Speicherplatzverbrauch</h3></div>

Da intern auf Tiefensuche zurückgegriffen wird, ist der Speicherplatzbedarf ähnlich dem der normalen Tiefensuche.

<div class="mw-heading mw-heading3"><h3 id="Laufzeit">Laufzeit</h3></div>

Da im schlimmsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssen, beträgt die Laufzeit von Iterativer Tiefensuche <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(\vert V\vert +\vert E\vert )}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\vert V\vert +\vert E\vert )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fafd762d516b0f9ebcb1fc41524000c2c610d4c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.65ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\vert V\vert +\vert E\vert )}" loading="lazy">, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vert V\vert }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vert V\vert }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a1b87251a78485894ca9c544f7582de9b5d4aedb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.081ex; height:2.843ex;" alt="{\displaystyle \vert V\vert }" loading="lazy"> für die Anzahl der Knoten und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vert E\vert }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vert E\vert }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e77aaf6d84a9a506ae76b7bd1418a7cf6ae68365.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.069ex; height:2.843ex;" alt="{\displaystyle \vert E\vert }" loading="lazy"> für die Anzahl der <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> im Graph steht.

<div class="mw-heading mw-heading3"><h3 id="Vollständigkeit">Vollständigkeit</h3></div>

Da sich Iterative Tiefensuche weder in unendlich langen Pfaden noch in <a href="Zyklus_(Graphentheorie)" title="Zyklus (Graphentheorie)">Zyklen</a> verlieren kann, ist der Algorithmus vollständig.

<div class="mw-heading mw-heading3"><h3 id="Optimalität">Optimalität</h3></div>

Iterative Tiefensuche ist optimal, falls alle Pfadkosten äquivalent sind, da Tiefensuche in diesem Fall den kürzesten Pfad zu einem Ziel findet. Sind die Pfadkosten jedoch nicht äquivalent, so kann es wie bei der Breitensuche dazu kommen, dass ein suboptimaler Pfad gewählt wird.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Stuart Russell, <a href="Peter_Norvig" title="Peter Norvig">Peter Norvig</a>: <a rel="nofollow" class="external text" href="http://aima.cs.berkeley.edu/">Artificial Intelligence: A Modern Approach</a>, 2. Auflage, 2002, Prentice Hall.</li>

<li>Thomas H. Cormen, <a href="Charles_Leiserson" class="mw-redirect" title="Charles Leiserson">Charles Leiserson</a>, <a href="Ronald_L._Rivest" title="Ronald L. Rivest">Ronald L. Rivest</a>, Clifford Stein: Introduction to Algorithms, MIT Press, 2nd edition 2001, ISBN 0-262-53196-8</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-04-30" href="https://de.wikipedia.org/wiki/?title=Iterative_Tiefensuche&oldid=255586558">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>